๐Ÿ‘ฉโ€๐Ÿ’ป 60063. ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ

@Seongukbaek Posted June 26, 2022 ยท Updated June 26, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ

๐Ÿ“ Logic

private void moveRobot() { ... }
  • BFS ๋ฐฉ์‹์œผ๋กœ board ํƒ์ƒ‰ํ•˜๋Š” ํ•จ์ˆ˜๋กœ, ์ด 3๋ฒˆ์˜ for ๋ฌธ์ด ์กด์žฌํ•œ๋‹ค.

    • ์ฒซ๋ฒˆ์งธ๋Š” ์ฃผ์–ด์ง„ ์ขŒํ‘œ๋กœ๋ถ€ํ„ฐ ์ด๋™ ๊ฐ€๋Šฅํ•œ ์ƒํ•˜์ขŒ์šฐ ์ขŒํ‘œ๋ฅผ queue์— ์ถ”๊ฐ€
    • ๋‘๋ฒˆ์งธ์™€ ์„ธ๋ฒˆ์žฌ๋Š” ๋กœ๋ด‡์˜ ์ขŒํ‘œ ์ค‘ ํ•˜๋‚˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ 90๋„ ํšŒ์ „ํ•˜์—ฌ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ขŒํ‘œ๋ฅผ queue์— ์ถ”๊ฐ€

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Robot { int x1; int y1; int dir; int cost; public Robot(int x1, int y1, int dir, int cost) { this.x1 = x1; this.y1 = y1; this.dir = dir; this.cost = cost; } } class Solution { static int[][] board; static int size; static int answer = 0; public int solution(int[][] board) { this.board = board; this.size = board.length; moveRobot(); return answer; } private void moveRobot() { int[] xRange = {0, 1, 0, -1}; int[] yRange = {1, 0, -1, 0}; // ํšŒ์ „ ์‹œ์— ์‚ฌ์šฉํ•  ๋ฒ”์œ„ ๋ฐฐ์—ด int[] rxRange = {-1, 1, 1, -1}; int[] ryRange = {1, 1, -1, -1}; boolean[][][] visited = new boolean[size][size][4]; // Queue์—๋Š” ์™ผ์ชฝ ์ขŒํ‘œ๋งŒ ์ถ”๊ฐ€ Queue<Robot> queue = new LinkedList<>(); int x1, y1, x2, y2, dir, cost; int nx1, ny1, nx2, ny2, ndir; queue.add(new Robot(0, 0, 0, 0)); visited[0][0][0] = true; while (!queue.isEmpty()) { Robot robot = queue.poll(); x1 = robot.x1; y1 = robot.y1; dir = robot.dir; cost = robot.cost; x2 = x1 + xRange[dir]; y2 = y1 + yRange[dir]; // ์ข…๋ฃŒ if (isFinish(x1, y1) || isFinish(x2, y2)) { answer = cost; return; } // ์ƒํ•˜์ขŒ์šฐ๋กœ ๋กœ๋ด‡ ์ด๋™ for (int r = 0; r < 4; r++) { nx1 = x1 + xRange[r]; ny1 = y1 + yRange[r]; nx2 = x2 + xRange[r]; ny2 = y2 + yRange[r]; if (!checkBoundary(nx1, ny1) || !checkBoundary(nx2, ny2)) continue; if (board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue; if (visited[nx1][ny1][dir]) continue; visited[nx1][ny1][dir] = true; queue.add(new Robot(nx1, ny1, dir, cost + 1)); } int rx, ry, tempDir; // x1, y1๋ฅผ ๊ธฐ์ค€์œผ๋กœ 90๋„ ํšŒ์ „ // ndir์€ 0(์˜ค๋ฅธ์ชฝ ๋Œ€๊ฐ์„  ์œ„), 1(์˜ค๋ฅธ์ชฝ ๋Œ€๊ฐ์„  ์•„๋ž˜), 2(์™ผ์ชฝ ๋Œ€๊ฐ์„  ์•„๋ž˜), 3(์™ผ์ชฝ ๋Œ€๊ฐ์„  ์œ„) ์ค‘ ํ•˜๋‚˜ for (int i = 1; i < 4; i += 2) { ndir = computeDir(dir, i); nx2 = x1 + xRange[ndir]; ny2 = y1 + yRange[ndir]; tempDir = (i == 1) ? ndir : dir; rx = x1 + rxRange[tempDir]; ry = y1 + ryRange[tempDir]; if (!checkBoundary(nx2, ny2) || !checkBoundary(rx, ry)) continue; if (board[nx2][ny2] == 1 || board[rx][ry] == 1) continue; if (visited[x1][y1][ndir]) continue; visited[x1][y1][ndir] = true; queue.add(new Robot(x1, y1, ndir, cost + 1)); } // ๋ฐ˜๋Œ€ ๋ฐฉํ–ฅ ์ฒ˜๋ฆฌ // x2, y2๋ฅผ ๊ธฐ์ค€์œผ๋กœ 90๋„ ํšŒ์ „ dir = computeDir(dir, 2); for (int i = 1; i < 4; i += 2) { ndir = computeDir(dir, i); nx1 = x2 + xRange[ndir]; ny1 = y2 + yRange[ndir]; tempDir = (i == 1) ? ndir : dir; rx = x2 + rxRange[tempDir]; ry = y2 + ryRange[tempDir]; ndir = (ndir + 2) % 4; if (!checkBoundary(nx1, ny1) || !checkBoundary(rx, ry)) continue; if (board[nx1][ny1] == 1 || board[rx][ry] == 1) continue; if (visited[nx1][ny1][ndir]) continue; visited[nx1][ny1][ndir] = true; queue.add(new Robot(nx1, ny1, ndir, cost + 1)); } } } private boolean checkBoundary(int x, int y) { return x >= 0 && x < size && y >= 0 && y < size; } private boolean isFinish(int x, int y) { return x == size - 1 && y == size - 1; } private int computeDir(int dir, int i) { return (dir + i) % 4; } }

โœ๏ธ Review

  • BFS๋ฅผ ์‚ฌ์šฉํ•ด ๋ชฉ์ ์ง€๊นŒ์ง€ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋ผ ํŒ๋‹จํ–ˆ๋‹ค. ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์‹œ์—๋Š” DFS, BFS๊ฐ€ ๊ฐ€๋Šฅํ•œ๋ฐ, BFS๊ฐ€ ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š”๋ฐ ๋” ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๋Š” ๊ฒƒ์„ ๋ฐฐ์› ๋˜ ๊ธฐ์–ต์ด ๋‚˜ BFS๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค.
  • ์•„์ด๋””์–ด ์ž์ฒด๋Š” ์‰ฝ๊ฒŒ ๋– ์˜ฌ๋ ธ๋‹ค๋งŒ, ๋กœ๋ด‡์˜ ์ขŒํ‘œ๊ฐ€ 2๊ฐœ์ธ ์ ๊ณผ ์ด์— ๋Œ€ํ•œ ํšŒ์ „ ๊ตฌํ˜„์— ์žˆ์–ด ์–ด๋ ค์› ๋‹ค ..
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€